package main

import "go-leetcode/leetcode/utils"

// 230. 二叉搜索树中第 K 小的元素
func main() {
	root := utils.SortedArrayToBST([]int{1, 2, 3, 4, 5})
	//k := 3

	nodeArr := staceScanNodeTreeForYILUN(root)

	for _, node := range nodeArr {
		println(node)
	}

}

type NodeInfo struct {
	node  *utils.TreeNode
	color int
}

func staceScanNodeTreeForYILUN(root *utils.TreeNode) []int { // 2025.02.23 练习, 模拟递归

	nodeInfos := []NodeInfo{{node: root, color: 0}}
	var result []int
	for len(nodeInfos) > 0 {
		nodeInfo := nodeInfos[len(nodeInfos)-1]
		nodeInfos = nodeInfos[:len(nodeInfos)-1]
		if nodeInfo.node == nil {
			continue
		}
		if nodeInfo.color == 1 {
			result = append(result, nodeInfo.node.Val)
		} else {
			nodeInfos = append(nodeInfos, NodeInfo{node: nodeInfo.node, color: 1})
			nodeInfos = append(nodeInfos, NodeInfo{node: nodeInfo.node.Right, color: 0})
			nodeInfos = append(nodeInfos, NodeInfo{node: nodeInfo.node.Left, color: 0})
		}
	}
	return result
}

func staceScanNodeTreeForDP(root *utils.TreeNode) []int { // 2025.02.23 练习, 模拟递归
	// 用栈模拟递归
	var arr []int

	stack := []*utils.TreeNode{root}

	for len(stack) > 0 {
		latestNode := stack[len(stack)-1]

		if latestNode.Left == nil { // 左边为空，自己出栈, 右子树进来
			stack = stack[:len(stack)-1]
			arr = append(arr, latestNode.Val)
			if latestNode.Right != nil {
				stack = append(stack, latestNode.Right)
			}
		} else {
			stack = append(stack, latestNode.Left)
			latestNode.Left = nil
		}
	}

	return arr
}

func kthSmallest1(root *utils.TreeNode, k int) int { // 2025.02.23 练习
	// 用栈模拟递归
	var stack []*utils.TreeNode

	for k > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}

		stack, root = stack[:len(stack)-1], stack[len(stack)-1]

		k--
		if k == 0 {
			return root.Val
		}
		root = root.Right
	}

	return 0
}

func kthSmallest(root *utils.TreeNode, k int) int {
	// 关键，搜索二叉树的搜索， 这样可以中序遍历，找到第K个直接返回了
	// 用栈模拟中序列遍历，小有难度
	var stack []*utils.TreeNode
	for k > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		// 开始出栈
		stack, root = stack[:len(stack)-1], stack[len(stack)-1]
		k--
		if k == 0 {
			return root.Val
		}

		root = root.Right
	}

	return 0
}

// 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
//
//示例 1：
//
//输入：root = [3,1,4,null,2], k = 1
//输出：1
//示例 2：
//
//输入：root = [5,3,6,2,4,null,null,1], k = 3
//输出：3
//
//提示：
//
//树中的节点数为 n 。
//1 <= k <= n <= 104
//0 <= Node.val <= 104
//
//进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
